MPEG
videokomprimering
Det finns nog ingen van användare av Internet i dag
som inte märkt av begränsningarna i överföringshastigheten.
Problemet kommer nog inte att bli mindre heller. I alla
fall inte om idéer som TV över Internet blir verklighet.
För att Internet och andra nätverk inte ska "slamma
igen" helt måste man komprimera stora filer som videofiler.

MPEG (Moving Pictures Expert Group) är en grupp som
sammanträder fyra gånger om året, en vecka åt gången och
fastställer videokomprimerings standarder. MPEG är ett
smeknamn för ISO/IEC JTC1 SC29 WG11. Hittills har man
kommit fram till standarderna MPEG 1, 2 och 4. MPEG 3
har också funnits men den integrerades i MPEG 2. Dessa är
optimerade för olika överföringshastigheter och kvalitet.
Själva komprimeringen är den samma hos alla typer av MPEG.
Det är en så kallad "lossy" komprimering. "Lossy" är engelska
och står för att man tappar något i innehållet när man
komprimerar. Man skalar helt enkelt bort information i bilden
som det mänskliga ögat ändå inte märker. Att man tappar
information är ett måste då motsvarigheten, "lossless"
komprimering bara kan komprimera upp till 2:1. Exakt vad det
mänskliga ögat kan och inte kan se är det självklart ingen som
vet. Något man däremot är säker på är att ögat är känsligare för
kontrastskillnader än nyansskillnader. Ögat är också mer
känsligt för lågfrekventa- än högfrekventa förändringar.

MPEG 1
MPEG 1 består av 5 varianter som alla ingår i ISO-standarden
ISO/IEC 11172. Den är skapad för komprimering av så kallade
progressiva videosekvenser på t ex CD-ROM. Progressiva
sekvenser har man när varje bild visar en komplett
ögonblicksbild av motivet. Motsatsen kallas sammanvävd
sekvens och där är informationen lagrad i två fält. Ett fält med
alla jämna rader och ett med alla udda. PAL, SECAM
och NTSC som är standarder för olika TV-signaler använder
alla sammanvävd sekvens. Det ger problem när man ska göra
om TV-signalen till en MPEG 1 sekvens. För TV-distribution
gav MPEG 1 också för dålig bildkvalitet p g a komprimerings
algoritmen skalade bort för mycket av datan.

MPEG 2
Därför utvecklades MPEG 2 som ger bättre bildkvalitet och
klarar av sammanflätade sekvenser. MPEG 2 kräver därför
också högre hastighet och större filer. Den används till bl a
DVD-video och Digital-TV.

MPEG 4
Det senaste tillskottet i MPEG-familjen heter MPEG 4. Den är
avsedd till videotelefoner och dyl. där överföringshastigheten
och kraven på bildkvaliteten är lägre. Här har man reducerat
antalet bilder/sekund till ca 10 st jämfört med MPEG 1 och
MPEG 2 där man vanligen har 24 bilder/sekund. TV i Sverige
(PAL) använder 50 fält/sekund. Eftersom ett fält bara
innehåller halva bilden betyder det att man har 25 helt nya
bilder per sekund.

Färgrymden
I MPEG använder man sig av färgrymden YCrCb, där Y
står för luminansen, eller ljusstyrkan, i en punkt och Cr och
Cb står för krominansen eller färgförhållandet. I
datorsammanhang i övrigt använder man sig oftast av RGB
där parametrarna står för mängden rött, grönt och blått i en
punkt. En fördel med YCrCb är att ljusstyrkan och
färgförhållandet är separerade från varandra. Eftersom att
ögat är mindre känsligt för skillnader i färgförhållandet
"subsamplar" man krominansparametrarna. Det betyder
att man tar bort t ex varannan krominansparameter och
på så vis får mindre data kvar.

Övergång från RGB till YCrCb grafiskt ill.

Det vanligaste förekommande krominansformatet kallas
4:2:0 och där har man tagit bort ¾ av färgförhållandena
utan att ögat uppfattar det som en nämnvärd försämring.
På det här viset har man skalat bort hälften av
informationsmängden. Det ingår dock inte i själva
MPEG-komprimeringen då MPEG utgår från videosekvenser
som representeras i denna färgrymd.



Komprimeringen

Bildtyper

I MPEG finns det tre olika typer av bilder. I-, P- och B-bilder.
I-bild ("intra coded picture", internt kodad bild): Denna typ av
bild kodas helt fristående utan referenser till andra bilder i
sekvensen. Bilden är dock uppdelad i block som kan referera
till varandra. Vid omstart av uppspelningen av sekvensen måste
uppspelningen börja på en sådan här bild. För att man ska kunna
spola i sekvensen bör det vara en I-bild ungefär var 0.4 sekund.

P-bild ("predictive coded picture", förutsagd bild): Denna typ
innehåller referenser till föregående bild. Det som inte går att
referera till föregående bild kodas som i I-bilderna.

B-bild ("biderctionally predictive coded picture",
tvåvägs-förutsagd bild): Denna bildtyp innehåller referenser till
föregående och nästkommande bild. Det gör den lite krångligare
då nästkommande bild måste dekomprimeras före B-bilden.
Avkodningen blir inte längre linjär utan man måste hoppa fram
och tillbaka. B-bilder används vid panoreringar där bilden kan
beskrivas som ett medelvärde av de två omgivande bilderna.
Hur ska man då koda en bestämd bild?
Några saker som algoritmen som bestämmer bildval skall ta
hänsyn till är:
Har det precis varit scenbyte? Då kan det vara svårt att hitta
likheter så välj att I-koda bilden.


När var det senast en I-bild? Var det ungefär 0.4 sekunder eller

10-12 bilder sedan så är det dags för en I-bild.

Är alla rörelser linjära? I sådana fall lämpar sig en B-bild bra.

Har det inte hänt så mycket sedan föregående bild? Då är nog en
P-bild en bra ide.

Det blir svårt att bestämma vilken bildtyp man ska använda när
t ex rörelserna är nästan linjära eller när bilden är ganska lik den
föregående. Därför är det enklast att bara bestämma sig för ett
visst mönster att följa vid kodningen. När det sedan kommer
ett scenbyte är det bara att avbryta mönstret och börja om med
en I-bild. Ett vanligt sådant mönster är
IBBPBBPBB IBBPBBPBB. Om man vill göra det ännu enklare
för sig kan man göra som på företaget Xing Technologies.
Där använder de sig bara av I-bilder. Sekvenserna blir över
dubbelt så stora då men det är betydligt enklare att både
komprimera och dekomprimera.

Rörelsekompensation
Rörelsekompensation görs bara för P- och B-bilder. För varje
block (vanligen 8*8 punkter) i en P-bild görs en sökning i
föregående bild efter ett tillräckligt likt block. Informationen i
blocket ersätts då med en vektor som beskriver hur mycket
blocket i referensbilden är förskjuten. En matris med feltermer
som beskriver vad som inte är sig likt behövs eventuellt.

Flödesschema över rörelsekompensation och kodning av P-bild.

För att snabba upp sökningen bör man ha följande punkter i
betänkande:
Det behövs ingen rörelsekompensation om bilden inte har
förändras överhuvudtaget sedan föregående bild.

Om alla matchningar hittills har gjorts med samma förskjutning
så kan man börja leta åt det hållet.

Vid panoreringar är det onödigt att leta efter de block som
tillkommit vid kanten på bilden.

Vilket är bäst: Bra matchningar eller sämre matchningar med
fler likadana rörelsevektorer? (Många likadana rörelsevektorer
går bättre att komprimera med Huffmankodningen senare i
processen)

Om det är en B-bild man kodar så behöver inte blocken i de
omgivande bilderna vara lika B-bildens block. Huvudsaken
är att deras medelvärden är likt blocket i B-bilden.
De uppkomna feltermer och block som inte gick att matcha går
nu igenom Den Diskreta Cosinustransformen, Kvantisering och
Sicksack-scanning. Det gör inte rörelsevektorerna.

Den Diskreta Cosinustransformen
Det är en transform som gör om alla block med parametrar till
lika stora frekvensblock. I översta vänstra hörnet av blocken
placeras de lågfrekventa parametrarna och frekvensen ökar
successivt mot det nedre högra hörnet i blocken.

Den Diskreta Cosinustransformen.

Kvantisering
Värderna i frekvensblocken divideras ner enligt en
kvantiseringsmatris och avrundas. På så vis får man många lika
värden som är tacksamma att Huffmankomprimera.
Ex:	binärt talsyst.       "vanliga" talsyst.
	101101           =  45 (6 bitar)
	1011               =  11 (kapa till 4 bitar)
	101                 =  5 (kapa till 3 bitar)
I Kvantiseringen tillkommer den största delen av felen in i
MPEG-sekvensen. Desto mer man kapar eller dividerar desto
större blir felet.

Sicksack-scanning
Här plockas blocken sönder till en vektor. En så kallad bitström.
Det gör man i ett speciellt sicksack-mönster. Detta för att
gruppera de lågfrekventa koefficienterna i början av vektorn.
Med ett 8*8 punkters block ser det ut så här:

Sicksack-scanning av ett 8*8 punkters block till en 64*1 vektor

Huffmankodningen
Både rörelsevektorerna och vektorerna från Sicksack-scanningen
entropitetskodas här. Det är egentligen ingen äkta
Huffmankodning. På engelska heter metoden "Variable Length
Coding" (VLC) och är en lätt modifierad variant av
Huffmankodning. Metoden går ut på att man bygger upp ett så
kallat Huffmanträd eller binärträd. Man börjar med att
rangordna parametrarna efter förekomst. Med sekvensen
0, 0, 0, 11, 0, 0, 23, 23, 23, 0, 0, 14, 11, 0, 0, 18, 18, 14, 18, 18
så blir rangordningen: 0 (9 st), 18 (4 st), 23 (3 st), 11 (2 st) och
14 (2 st). Därefter låter man de två ovanligaste parametrarna
(11 och 14) bli de två yttersta lövnoderna i trädet:
De två lövnoderna skall nu ses som ett objekt, A, med förekomsten 2 st + 2st = 4st

Nu upprepar man proceduren och tar ut de två ovanligaste
parametrarna (23 och trädet A). Så fortsätter man så här tills
man har ett helt träd med den vanligaste parametern i toppen.
Huffman-träd

Varje vänster gren i trädet låter man motsvaras av biten "0" och
varje högergren av biten "1". Siffrorna kommer då att kunna
ersättas av den bitsekvens som beskriver vägen till dem genom
trädet: 0="0", 18="10", 23="110", 14="1110" och 11="1111".
Hela sekvensen blir då: "0001111001101101100011101111001"
vilket är 42 bitar. Där till kommer naturligtvis datan som
innehåller själva Huffmanträdet men förtjänsten är ändock
stor. Datorn lagrar normalt alla värden binärt enligt ASCII-tabellen
och då behövs det 8 bitar per tecken. Okodad skulle alltså
sekvensen ta 8*20 = 160 bitar.

Dekomprimering
Nu är MPEG-sekvensen färdig kodad. Dekomprimeringen går till på
exakt samma sätt bortsett från att man gör allt baklänges.

Komprimeringsgraden
Den optimala komprimeringen för MPEG 2 ger en bitström med
ungefär 1,2 bitar/bildpunkt för I-bilder och 0,35 bitar/bildpunkt
för P- och B-bilder. Det innebär en komprimeringsgrad på 6:1
respektive 20:1. Vid lagom blandning av bildtyperna blir det en
total komprimering på drygt 18:1. Det går naturligtvis att
komprimera mycket mer än så men då börjar det dyka upp
synliga fel.


Referenser:

Che-Cher, Chen. "Survey and Implementation of A Distributed MPEG Video Player."
[http://hpc.ee.ntu.edu.tw/~murphy/reports/MMnet/final/MMFinalReport.html]. Aug 1998.

Okänd. "KOMPRIMERING och FILFORMAT."
[http://www.tfe.umu.se/courses/systemteknik/Multimed1/video/komp.html]. Mar 1998.

Okänd. "Komprimering på Internet."
[http://www.island.liu.se/~i94chrob/kom_pa_internet_slutkomm.html].
Apr 1998.

Okänd. "MOVING PICTURE EXPERT GROUP (MPEG)."
[http://www.hogent.be/chroma/MPEGs.html].
Jun 1997.

Söderström, Kjell. "GRAFISKA FILFORMAT."
[http://www.nti.se/~kjell/btt/filformat.html]. Maj 1997.

Terje, Dalen. "Introduksjon til MPEG-1."
[http://multimedia.itek.norut.no/LAVA/MPEG/MPEG1-intro.html].
Okt 1995.

Vinjar, Anders. "KVANTISERING."
[http://www.notam.uio.no/open/settekasse/DSP/DSP/node4.html]. Nov 1996.